import common.TrieNode;

/**
 * 208. 实现 Trie (前缀树) Implement Trie Prefix Tree
 * https://leetcode-cn.com/problems/implement-trie-prefix-tree/
 */
/**
 * Class: Trie
 * 实现前缀树（字典树）数据结构，用于高效存储和检索字符串集合
 * 
 * Args:
 *   - root: TrieNode类型，表示前缀树的根节点
 * 
 * Methods:
 *   - insert(String word): 向前缀树中插入一个单词
 *   - search(String word): 搜索前缀树中是否存在完整单词
 *   - startsWith(String prefix): 搜索前缀树中是否存在以指定前缀开头的单词
 *   - find(String word): 内部方法，用于查找单词或前缀
 * 
 * Time Complexity:
 *   - insert: O(n), n为单词长度
 *   - search: O(n), n为单词长度
 *   - startsWith: O(n), n为前缀长度
 * 
 * Space Complexity:
 *   - O(m*n), m为字符集大小（26个字母），n为所有单词的总长度
 */



class Trie {
    private TrieNode root;                   // 根节点

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for(char c : word.toCharArray()){
            int idx = c - 'a';  // 计算字母索引（0~25）
            if (node.children[idx] == null){
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        return find(word) == 2;
    }
    
    public boolean startsWith(String prefix) {
        return find(prefix) != 0;
    }

    private int find(String word){
      TrieNode node = root;
        for(char c : word.toCharArray()){
            int idx = c - 'a';  // 计算字母索引（0~25）
            if (node.children[idx] == null){
                return 0;
            }
            node = node.children[idx];
        }
        return node.isEnd ? 2 : 1;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */